home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 1997 #1 / Amiga Plus CD - 1997 - No. 01.iso / pd / programmierung / proasm / routines / qsort.r < prev    next >
Text File  |  1994-08-05  |  4KB  |  176 lines
  1.  
  2. ;---;  qsort.r  ;--------------------------------------------------------------
  3. *
  4. *    ****    QuickSort    ****
  5. *
  6. *    Author        Daniel Weber
  7. *    Version        0.86
  8. *    Last Revision    14.07.93
  9. *    Identifier    qst_defined
  10. *       Prefix        qst_    (quicksort)
  11. *                 ¯    ¯  ¯
  12. *    Functions    qsort        - sorts a given array of longwords
  13. *
  14. ;------------------------------------------------------------------------------
  15.  
  16.     IFND    qst_defined
  17. qst_defined    SET    1
  18.  
  19. ;------------------
  20. qst_oldbase    equ __BASE
  21.     base    qst_base
  22. qst_base:
  23.  
  24. ;------------------
  25.     opt    sto,o+,ow-,q+,qw-
  26.  
  27.  
  28. ;------------------------------------------------------------------------------
  29. *
  30. * qst_randomentry
  31. *
  32. * this macro may be used to fill an array with random values
  33. * (it might be very useful to test the quicksort algorithm below):
  34. *
  35. * .fillarray:    REPT    100        ;fills longword array with 100 entries
  36. *        qst_randomentry
  37. *        ENDR
  38. *
  39. * note that the use of this macro takes its time to be assembled...
  40. *
  41. ;------------------------------------------------------------------------------
  42.  
  43. qst_randomentry    MACRO
  44.         IFND    .seed
  45.         IFC    '','\1'
  46. .seed        SET    1993+_mcount        ;random value + macro number
  47.         ELSE
  48. .seed        SET    \1            ;user defined start value
  49.         ENDC
  50.         ENDC
  51.  
  52. .a        SET    16807            ;a:=16807
  53. .m        SET    2147483647        ;m:=2147483647
  54. .q        SET    .m/.a            ;q:=m DIV a
  55. .r        SET    .m\.a            ;r:=m MOD a
  56. .seed        SET    .a*(.seed\.q)-.r*(.seed/.q) ;seed:=a*(seed MOD q)-r*(seed DIV q)
  57.         IFLE    .seed            ;IF seed<= 0 THEN
  58. .seed        SET    .seed+.m        ;   seed:=seed+m
  59.         ENDC                ;END
  60.         dc.l    .seed&$7fffffff        ;only positive #
  61.         ENDM
  62.  
  63.  
  64. ;------------------------------------------------------------------------------
  65. *
  66. * qsort        - QuickSort
  67. *
  68. * INPUT:    D0    #of elements to be sorted
  69. *        A0    start address of array
  70. *
  71. * NOTE:        all register will be unaffected
  72. *
  73. * Memeory use:    O(log2 N)
  74. *
  75. ;------------------------------------------------------------------------------
  76.  
  77. qsort:    apushm
  78.     subq.l    #1,d0
  79.     ble    qst_quickend
  80.  
  81.     move.l    a0,a2
  82.     lsl.l    #2,d0
  83.     lea    -4+4(a2,d0.l),a3
  84.  
  85.     pea    qst_quickend(pc)    ;a 'bsr.s' will be shorter, but the
  86.                     ;apushm/apopm would then be sensless...
  87. ;
  88. ; a2: first element
  89. ; a3: last element
  90. ;
  91. qst_quick:
  92.     movem.l    a0/a1,-(a7)
  93. qst_quick2:
  94. ;*    cmp.l    $110,a7            ;just for tests
  95. ;*    bge.s    ..            ;just for tests
  96. ;*    move.l    a7,$110            ;just for tests
  97. ;*..:
  98.     cmp.l    a2,a3            ;don't sort if there are no, one, or
  99.     bls.s    .out            ;a negative #of elements
  100.  
  101. ;*    addq.l    #1,$120            ;just for tests
  102.  
  103.     move.l    a3,d0            ;x:= a[(l+r) DIV 2];
  104.     sub.l    a2,d0
  105.     lsr.l    #1,d0
  106.     and.b    #$fc,d0
  107.     move.l    (a2,d0.l),d1        ;the middle element
  108.  
  109.     move.l    a2,a0            ;i:=l
  110.     lea    4(a3),a1        ;j:=r (+1 for the predecrement ea below)
  111.                     ;REPEAT
  112. 0$:    cmp.l    (a0)+,d1        ;WHILE a[i]<x DO INC(i) END
  113.     bgt.s    0$            ;
  114.     subq.l    #4,a0            ;
  115.  
  116. 1$:    cmp.l    -(a1),d1        ;WHILE a[j]>x DO DEC(j) END
  117.     blt.s    1$            ;
  118.  
  119. 2$:    cmp.l    a0,a1            ;IF i<=j THEN
  120.     blt.s    3$            ;
  121. .swap:    move.l    (a0),d0            ;swap a[i],a[j]
  122.     move.l    (a1),(a0)+        ;INC(i)
  123.     move.l    d0,(a1)            ;DEC(j) END  (DEC will be done above
  124.  
  125.     cmp.l    a0,a1            ;('-(a1)') or some lines below...)
  126.     bgt.s    0$            ;UNTIL i>j
  127.     subq.l    #4,a1            ;(DEC(j))
  128.  
  129. 3$:    move.l    a1,d0
  130.     sub.l    a2,d0            ;#of elements *4 in the left side
  131.     move.l    a3,d1
  132.     sub.l    a0,d1            ;#of elements *4 in the right side
  133.     cmp.l    d0,d1
  134.     bge.s    .bigright
  135. ;
  136. ; this is the recursive part of this quicksort.
  137. ; to keep the stack usage as small as possible only the smaller
  138. ; part will be called recursively and the larger non-recursively.
  139. ;
  140. .bigleft:                ;left side is bigger
  141.     move.l    a2,-(a7)
  142.     move.l    a0,a2
  143.     bsr    qst_quick        ;QuickSort(j,r)
  144.     move.l    (a7)+,a2
  145.     move.l    a1,a3
  146.     bra    qst_quick2        ;QuickSort(l,j)
  147.  
  148.  
  149. .bigright:                ;right side is bigger
  150.     move.l    a3,-(a7)
  151.     move.l    a1,a3
  152.     bsr    qst_quick        ;QuickSort(l,j)
  153.     move.l    (a7)+,a3
  154.     move.l    a0,a2
  155.     bra    qst_quick2        ;QuickSort(j,r)
  156.  
  157. .out:    movem.l    (a7)+,a0/a1
  158.     rts
  159.  
  160.  
  161. ;--------------------------------------
  162. qst_quickend:                ;end quicksort
  163.     apopm    a7            ;
  164.     rts
  165.  
  166. ;--------------------------------------------------------------------
  167.  
  168.     base    qst_oldbase
  169.     opt    rcl
  170.  
  171. ;------------------
  172.     ENDIF
  173.  
  174.  end
  175.  
  176.